# 1.给定两个字符串，判断s是否为t的重新排列后的单词
class Solution:
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        # solution1
        # ss = list(s)
        # tt = list(t)
        # ss.sort()
        # tt.sort()
        # return ss == tt

        # solution2
        # return sorted(list(s)) == sorted(list(t))

        # solution3
        dict1 = {}  # {'a':1, 'b':2}
        dict2 = {}
        for ch in s:
            dict1[ch] = dict1.get(ch, 0) + 1
        for ch in t:
            dict2[ch] = dict2.get(ch, 0) + 1
        return dict1 == dict2

# 2.给定一个m*n的二维列表，查找一个数是否存在，列表的特性如下：
# 每一行的列表从左到右已经排序好
# 每一行第一个数比上一行最后一个数大

# [
#     [1,3,5,7],
#     [10,11,16,20],
#     [23,30,34,50]
# ]
class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: list[list[int]]
        :type target: int
        :rtype: bool
        """
        # solution1-O(m*n)
        # for line in matrix:
        #     if target in line:
        #         return True
        # return False

        # solution2-将二维数组当成一维数据利用二分搜索
        h = len(matrix)
        if h == 0:
            return False
        w = len(matrix[0])
        if w == 0:
            return False
        left = 0
        right = w * h - 1
        while left <= right:
            mid = (left + right) // 2
            i = mid // w    # row
            j = mid % w     # column
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] < target:
                left = mid + 1
            else:
                right = mid - 1
        return False

# 3.给定一个列表和一个整数，设计算法找到两个数的下标，使得两个数之和为给定的整数，保证肯定仅有一个结果
# 例如，列表[1,2,5,4]与目标整数3，1+2=3，结果为(0,1)
class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n = len(nums)
        for i in range(n):
            for j in range(i):
                if nums[i] + nums[j] == target:
                    return sorted([i, j])